class Solution
{
public:
    int maxSubarraySumCircular(vector<int> &nums)
    {
        int n = nums.size();
        int sum = accumulate(nums.begin(), nums.end(), 0);

        vector<int> maxSubDp(n);
        vector<int> minSubDp(n);
        maxSubDp[0] = nums[0];
        minSubDp[0] = min(0, nums[0]);

        int maxSub = nums[0];
        int minSub = 0;
        for (int i = 1; i < n; ++i)
        {
            if (maxSubDp[i - 1] > 0)
            {
                maxSubDp[i] = maxSubDp[i - 1] + nums[i];
            }
            else
            {
                maxSubDp[i] = nums[i];
            }

            if (minSubDp[i - 1] + nums[i] < 0)
            {
                minSubDp[i] = minSubDp[i - 1] + nums[i];
            }
            else
            {
                minSubDp[i] = 0;
            }

            maxSub = max(maxSub, maxSubDp[i]);
            minSub = min(minSub, minSubDp[i]);
        }
        if (maxSub <= 0)
        {
            return maxSub;
        }
        return max(maxSub, sum - minSub);
    }
};